package com.zhengb.algorithmdemo.leetcode.linklist.easy;

import com.zhengb.algorithmdemo.leetcode.linklist.ListNode;

import java.util.Stack;

/**
 * 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * https://leetcode-cn.com/problems/reverse-linked-list/
 *
 * @author zhengbo
 * @date 2020/3/11
 */
public class ReverseList {

    public static ListNode reverseListWithPoint(ListNode head) {

        ListNode curNode = head;

        ListNode preNode = null;

        ListNode tempNode = null;

        while (curNode != null) {
            tempNode = curNode.next;

            curNode.next = preNode;

            preNode = curNode;
            curNode = tempNode;
        }
        return preNode;
    }


    public static ListNode reverseListWithStack(ListNode head) {

        if (head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();

        ListNode curNode = head;
        stack.push(curNode);
        while ((curNode = curNode.next) != null) {
            stack.push(curNode);
        }

        if (stack.size() == 1) {
            return stack.pop();
        }

        ListNode headNode = stack.pop();

        curNode = headNode;

        while (!stack.isEmpty()) {
            curNode.next = stack.pop();

            curNode = curNode.next;
        }
        curNode.next = null;

        return headNode;
    }

    public static void main(String[] args) {

        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);

        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        five.next = null;

//        ListNode headNode = reverseListWithStack(one);

        ListNode headNode = reverseListWithPoint(one);

        System.out.println(headNode);
    }
}
